from typing import List


class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = {}
        indegree = {}
        # 初始化图
        for word in words:
            for c in word:
                graph[c] = []

        # 建立图 
        for i in range(len(words) - 1):
            bf, af = words[i], words[i + 1]
            j, min_len = 0, min(len(bf), len(af))
            while j < min_len:
                if bf[j] != af[j]:
                    graph[bf[j]].append(af[j])
                    indegree[af[j]] = indegree[af[j]] + 1 if af[j] in indegree else 1
                    break
                j += 1
            if j == min_len and len(bf) > len(af):
                return ''

        # 拓扑排序
        queue = []
        for key in graph:
            if key not in indegree:
                queue.append(key)

        ans = ''
        while len(queue) > 0:
            c = queue.pop(0)
            ans += c
            for n in graph[c]:
                indegree[n] -= 1
                if indegree[n] == 0:
                    queue.append(n)

        return ans if len(ans) == len(graph) else ''